// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

// 算法思路总结：
// 1. 递归查找从根节点到目标节点的路径
// 2. 使用栈存储路径上的所有节点
// 3. 比较两条路径找到最后一个公共节点
// 4. 通过弹出栈顶元素对齐路径长度
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <stack>
#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

TreeNode* FindNum(TreeNode* root, int num)
{
    if (root == nullptr)
    {
        return nullptr;
    }

    if (root->val == num)
    {
        return root;
    }

    TreeNode* left = FindNum(root->left, num);
    if (left != nullptr)
    {
        return left;
    }

    return FindNum(root->right, num);
};

// class Solution 
// {
// public:
//     bool Find(TreeNode* root, TreeNode* x)
//     {
//         if (root == nullptr)
//         {
//             return false;
//         }

//         if (root == x)
//         {
//             return true;
//         }

//         return Find(root->left, x) || Find(root->right, x);
//     }

//     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
//     {
//         if (root == p || root == q)
//         {
//             return root;
//         }

//         bool isPleft, isPright, isQleft, isQright;
//         isPleft = Find(root->left, p);
//         isPright = !isPleft;
//         isQleft = Find(root->left, q);
//         isQright = !isQleft;

//         if (isPleft && isQleft)
//         {
//             return lowestCommonAncestor(root->left, p, q);
//         }
//         else if (isPright && isQright)
//         {
//             return lowestCommonAncestor(root->right, p, q);
//         }
//         else if (isPleft && isQright)
//         {
//             return root;
//         }
//         else if (isPright && isQleft)
//         {
//             return root;
//         }

//         return nullptr;
//     }
// };

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        if (root == nullptr)
        {
            return false;
        }

        path.push(root);

        if (root == x)
        {
            return true;
        }

        if (GetPath(root->left, x, path))
        {
            return true;
        }

        if (GetPath(root->right, x, path))
        {
            return true;
        }

        path.pop();
        
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if (root == nullptr)
        {
            return nullptr;
        }

        stack<TreeNode*> pPath, qPath;
        GetPath(root, p, pPath);
        GetPath(root, q, qPath);

        stack<TreeNode*>* longPath = &pPath, *shortPath = &qPath;
        if (longPath->size() < shortPath->size())
        {
            longPath = &qPath;
            shortPath = &pPath;
        }

        while (longPath->size() != shortPath->size())
        {
            longPath->pop();
        }

        while (longPath->top() != shortPath->top())
        {
            longPath->pop();
            shortPath->pop();
        }
        
        return longPath->top();
    }
};

int main()
{
    vector<string> tree1 = {"3","5","1","6","2","0","8","null","null","7","4"};
    int p1 = 5, q1 = 1;

    vector<string> tree2 = {"3","5","1","6","2","0","8","null","null","7","4"};
    int p2 = 5, q2 = 4;

    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    auto pp1 = FindNum(root1, p1);
    auto qq1 = FindNum(root1, q1);

    auto pp2 = FindNum(root2, p2);
    auto qq2 = FindNum(root2, q2);

    cout << (sol.lowestCommonAncestor(root1, pp1, qq1)->val) << endl;
    cout << (sol.lowestCommonAncestor(root2, pp2, qq2)->val) << endl;

    return 0;
}